package main_package;

import genetic_algorithm.Chromosome;
import genetic_algorithm.GA;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Random;

/**
 * this class implements the GA algorithm for solving the Griddlers problem
 */
public class GA_griddlers_alg implements GA
{
	// the population size
	int POPULATION_SIZE=100;
	// the percentage for performing a mutation an a child chromosome
	int MUTATION_RATE=10;
	// the number of generations
	int NUM_OF_GENERATIONS=2000;
	// the percentage of performing crossover between two parents 
	int CROSSOVER_RATE=95;
	// the number of row constraints
	int BOARD_SIZE_ROW;
	// the number of col constraints
	int BOARD_SIZE_COL;

	/**
	 * this function run the GA algorithm for the Griddlers problem
	 * @param row_cons - the row constraints
	 * @param col_cons - the column constraints
	 * @throws IOException 
	 */
	public void run_alg(ArrayList<ArrayList<Integer>> row_cons, ArrayList<ArrayList<Integer>> col_cons) throws IOException
	{
		// Initialize variables
		GriddlersChromosome.row_cons = row_cons;
		GriddlersChromosome.col_cons = col_cons;
		BOARD_SIZE_ROW = row_cons.size();
		BOARD_SIZE_COL = col_cons.size();
		int gen = 100;
		// get the fitness of the best solution
		int right_solution_fitness = calcRight(row_cons, col_cons);

		// initialize the population
		ArrayList<Chromosome> population=initiate_population(POPULATION_SIZE);

		Random r = new Random();
		int count=0;
		ArrayList<Chromosome> selected;
		ArrayList<Chromosome> children;

		boolean foundSolution=false;
		// for each generation
		while(count<NUM_OF_GENERATIONS)
		{	
			Chromosome best=getMaxAndRemoveWorst(population, right_solution_fitness);
			// the case that the GA found the solution for this Griddler
			if(best.evaluateFitness()== right_solution_fitness)
			{
				foundSolution=true;
				break;
			}

			// the case that 'gen' number of iterations have passed
			if(count == gen)
			{
				System.out.println("gen: " + count + " and best fit so far: " + best.evaluateFitness());
				gen+=100;
			}

			population.remove(best);
			Chromosome second_best=getMaxAndRemoveWorst(population, right_solution_fitness);
			population.add(best);

			// selecting the parents for crossover
			selected=selection(population);
			population.clear();

			// initiating the not picked array to all the indexes
			ArrayList<Integer> indexes_not_chosen_yet=new ArrayList<Integer>();
			for(int i=0;i<POPULATION_SIZE-2;i++)
				indexes_not_chosen_yet.add(i);
			int index1,index2,first_index, second_index;

			// for every random two parents from the selection array
			for(int i=0;i<POPULATION_SIZE-2;i+=2)
			{
				index1=r.nextInt(indexes_not_chosen_yet.size());
				first_index=indexes_not_chosen_yet.get(index1);
				indexes_not_chosen_yet.remove(index1);
				index2=r.nextInt(indexes_not_chosen_yet.size());
				second_index=indexes_not_chosen_yet.get(index2);
				indexes_not_chosen_yet.remove(index2);

				// performing crossover between two parents
				children=crossover(selected.get(second_index),selected.get(first_index));
				// adding those new children to the next population
				population.addAll(children);
			}

			// transfering the two best chromosome from this generation to the next one
			population.add(best);
			population.add(second_best);
			count++;
		}

		// getting the best board solution the GA has found
		Chromosome final_solution=getBestSolution(population);
		System.out.println("our GA fitness "+ final_solution.evaluateFitness());
		// creating the result CSV file
		printResult(final_solution);

		// the case that a solution has not been found
		if(!foundSolution)
			System.out.println("no solution found");
		// the case that a solution has been found
		else
			System.out.println("found solution in "+count+" iterations");
	}

	/*
	 * this function writes the best solution board into a csv file
	 * @param final_solution - the best chromosome
	 * @throws IOException
	 */
	private void printResult(Chromosome final_solution) throws IOException
	{
		FileWriter fw = new FileWriter("result.csv");
		BufferedWriter bw = new BufferedWriter(fw);
		ArrayList<ArrayList<Integer>> sol = final_solution.getData();
		ArrayList<Integer> row;

		// for every row
		for (int i = 0; i < sol.size(); i++) 
		{
			row = sol.get(i);
			// for every cell in the row
			for (int j = 0; j < row.size(); j++) 
			{
				// write the cell into the file
				bw.write(String.valueOf(row.get(j).intValue()));

				// the case that this is not the last cell in the row
				if(j != (row.size()-1))
				{
					bw.write(',');
				}
			}
			bw.newLine();
		}

		bw.close();
		fw.close();
	}

	/*
	 * this function return the fitness of the correct solution to this griddler
	 * @param row_cons - the row constrints
	 * @param col_cons - the col constrints
	 * @return - the fitness of the correct solution
	 */
	private int calcRight(ArrayList<ArrayList<Integer>> row_cons, ArrayList<ArrayList<Integer>> col_cons)
	{
		int right = 0;
		// for every row constraint
		for (int i = 0; i < row_cons.size(); i++) 
		{
			right += BOARD_SIZE_COL*(row_cons.get(i).size());
		}

		// for every col constraint
		for (int i = 0; i < col_cons.size(); i++) 
		{
			right += BOARD_SIZE_ROW*(col_cons.get(i).size());
		}

		System.out.println("the right solution fitness is: " + right);
		return right;
	}

	/**
	 * this function run the darwin GA algorithm for the Griddlers problem
	 * @param row_cons - the row constraints
	 * @param col_cons - the column constraints
	 * @throws IOException 
	 */
	public void run_darwin_alg(ArrayList<ArrayList<Integer>> row_cons,
			ArrayList<ArrayList<Integer>> col_cons) throws IOException
			{
		// Initialize variables
		GriddlersChromosome.row_cons = row_cons;
		GriddlersChromosome.col_cons = col_cons;
		BOARD_SIZE_ROW = row_cons.size();
		BOARD_SIZE_COL = col_cons.size();
		int gen = 100;
		// get the fitness of the best solution
		int right_solution_fitness = calcRight(row_cons, col_cons);

		// initialize the population
		ArrayList<Chromosome> population=initiate_population(POPULATION_SIZE);
		ArrayList<Chromosome> population2;

		Random r = new Random();
		int count=0;
		ArrayList<Chromosome> selected;
		ArrayList<Chromosome> children;
		ArrayList<Chromosome> bests;
		ArrayList<Chromosome> bests2;

		boolean foundSolution=false;
		// for each generation
		while(count<NUM_OF_GENERATIONS)
		{	
			// performing an optimazation on the population
			population2 = opt(population);

			bests=getMaxAndRemoveWorstDarwin(population, population2, right_solution_fitness);
			// the case that the GA found the solution for this Griddler
			if(bests.get(0).evaluateFitness()== right_solution_fitness)
			{
				foundSolution=true;
				break;
			}

			// the case that 'gen' number of iterations have passed
			if(count == gen)
			{
				System.out.println("gen: " + count + " and best fit so far: " + bests.get(0).evaluateFitness());
				gen+=100;
			}


			population.remove(bests.get(0));
			population2.remove(bests.get(1));
			bests2=getMaxAndRemoveWorstDarwin(population, population2, right_solution_fitness);
			population.add(bests.get(0));
			population2.add(bests.get(1));

			// selecting the parents for crossover
			selected=selection_darwin(population, population2);
			population.clear();

			// initiating the not picked array to all the indexes
			ArrayList<Integer> indexes_not_chosen_yet=new ArrayList<Integer>();
			for(int i=0;i<POPULATION_SIZE-2;i++)
				indexes_not_chosen_yet.add(i);
			int index1,index2,first_index, second_index;

			// for every random two parents from the selection array
			for(int i=0;i<POPULATION_SIZE-2;i+=2)
			{
				index1=r.nextInt(indexes_not_chosen_yet.size());
				first_index=indexes_not_chosen_yet.get(index1);
				indexes_not_chosen_yet.remove(index1);
				index2=r.nextInt(indexes_not_chosen_yet.size());
				second_index=indexes_not_chosen_yet.get(index2);
				indexes_not_chosen_yet.remove(index2);

				// performing crossover between two parents
				children=crossover(selected.get(second_index),selected.get(first_index));
				// adding those new children to the next population
				population.addAll(children);
			}

			// transfering the two best chromosome from this generation to the next one
			population.add(bests.get(0));
			population.add(bests2.get(0));
			count++;
		}

		// getting the best board solution the GA has found
		Chromosome final_solution=getBestSolution(population);
		System.out.println("our GA fitness "+ final_solution.evaluateFitness());
		// creating the result CSV file
		printResult(final_solution);

		// the case that a solution has not been found
		if(!foundSolution)
			System.out.println("no solution found");
		// the case that a solution has been found
		else
			System.out.println("found solution in "+count+" iterations");

			}

	/*
	 * this function selects the parents for the crossover operation
	 * (fitness checks are according to the optimized population)
	 * @param population - the current population
	 * @param population2 - the optimized population
	 * @return - the selected parents for the crossover
	 */
	private ArrayList<Chromosome> selection_darwin(
			ArrayList<Chromosome> population, ArrayList<Chromosome> population2) throws IOException {
		// calculating the average fitness
		double avg=calcAvgFitness(population2);
		int N=population2.size();
		int T = N;

		Random r=new Random();
		// get a random number
		double num=r.nextInt(T);
		double sum = 0.0;
		int j;

		ArrayList<Chromosome> selected=new ArrayList<Chromosome>();

		// choose N parents
		for(int i=0;i<N;i++)
		{
			// for each chromosome in the population
			for(j=0;j<N;j++)
			{
				// add the exp value to the sum
				sum+=ExpVal(j,population2,avg);
				// the case that this "j" chromosome was selected
				if(sum>num)
				{	
					selected.add(population.get(j));
					// change in fixed distance
					num = (num+((double)T/N)) % T;
					sum = 0.0;
					break;
				}
			} 
		}

		return selected;
	}

	/*
	 * this function returns the chromosome with the best fitness in the population
	 * and removes the worst one (fitness checks are according to the optimized population)
	 * @param population - the current population
	 * @param population2 - the optimized population
	 * @param right_solution_fitness - the best fitness possiable
	 * @return - the best chromosome for the original population and the one in
	 * the optimized
	 */
	private ArrayList<Chromosome> getMaxAndRemoveWorstDarwin(
			ArrayList<Chromosome> population,
			ArrayList<Chromosome> population2, int right_solution_fitness) {
		int max_fitness=-1;
		int max_index=-1;

		int min_fitness = right_solution_fitness+10;
		int min_index=-1;

		// for every chromosome in the population 
		for(int i=0;i<population2.size();i++)
		{
			// the case that this chromosome's fitness is bigger then the current maximal
			if(population2.get(i).evaluateFitness()>max_fitness)
			{
				// update the maxium fitness
				max_fitness=(int) population2.get(i).evaluateFitness();
				max_index=i;
			}

			// the case that this chromosome's fitness is lower then the current minimal
			if(population2.get(i).evaluateFitness()<min_fitness)
			{
				// update the minimum fitness
				min_fitness=(int) population2.get(i).evaluateFitness();
				min_index=i;
			}
		}

		ArrayList<Chromosome> bests = new ArrayList<Chromosome>();

		// the case that the whole population has the same fitness
		if(max_index == min_index)
		{
			bests.add(population.get(1));
			bests.add(population2.get(1));
			// remove the worst
			population.remove(0);
			// remove the worst
			population2.remove(0);
		}
		// the case that the whole population doesn't have the same fitness
		else
		{
			bests.add(population.get(max_index));
			bests.add(population2.get(max_index));
			// remove the worst
			population.remove(min_index);
			// remove the worst
			population2.remove(min_index);
		}
		return bests;
	}

	/**
	 * this function run the lamark GA algorithm for the Griddlers problem
	 * @param row_cons - the row constraints
	 * @param col_cons - the column constraints
	 * @throws IOException 
	 */
	public void run_lamark_alg(ArrayList<ArrayList<Integer>> row_cons,
			ArrayList<ArrayList<Integer>> col_cons) throws IOException {
		// Initialize variables
		GriddlersChromosome.row_cons = row_cons;
		GriddlersChromosome.col_cons = col_cons;
		BOARD_SIZE_ROW = row_cons.size();
		BOARD_SIZE_COL = col_cons.size();
		int gen = 100;
		// get the fitness of the best solution
		int right_solution_fitness = calcRight(row_cons, col_cons);

		// initialize the population
		ArrayList<Chromosome> population=initiate_population(POPULATION_SIZE);

		Random r = new Random();
		int count=0;
		ArrayList<Chromosome> selected;
		ArrayList<Chromosome> children;

		boolean foundSolution=false;
		// for each generation
		while(count<NUM_OF_GENERATIONS)
		{	
			// performing an optimization on the population
			population = opt(population);

			Chromosome best=getMaxAndRemoveWorst(population, right_solution_fitness);
			// the case that the GA found the solution for this Griddler
			if(best.evaluateFitness()== right_solution_fitness)
			{
				foundSolution=true;
				break;
			}

			// the case that 'gen' number of iterations have passed
			if(count == gen)
			{
				System.out.println("gen: " + count + " and best fit so far: " + best.evaluateFitness());
				gen+=100;
			}

			population.remove(best);
			Chromosome second_best=getMaxAndRemoveWorst(population, right_solution_fitness);
			population.add(best);

			// selecting the parents for crossover
			selected=selection(population);
			population.clear();

			// initiating the not picked array to all the indexes
			ArrayList<Integer> indexes_not_chosen_yet=new ArrayList<Integer>();
			for(int i=0;i<POPULATION_SIZE-2;i++)
				indexes_not_chosen_yet.add(i);
			int index1,index2,first_index, second_index;

			// for every random two parents from the selection array
			for(int i=0;i<POPULATION_SIZE-2;i+=2)
			{
				index1=r.nextInt(indexes_not_chosen_yet.size());
				first_index=indexes_not_chosen_yet.get(index1);
				indexes_not_chosen_yet.remove(index1);
				index2=r.nextInt(indexes_not_chosen_yet.size());
				second_index=indexes_not_chosen_yet.get(index2);
				indexes_not_chosen_yet.remove(index2);

				// performing crossover between two parents
				children=crossover(selected.get(second_index),selected.get(first_index));
				// adding those new children to the next population
				population.addAll(children);
			}

			// transfering the two best chromosome from this generation to the next one
			population.add(best);
			population.add(second_best);
			count++;
		}

		// getting the best board solution the GA has found
		Chromosome final_solution=getBestSolution(population);
		System.out.println("our GA fitness "+ final_solution.evaluateFitness());
		// creating the result CSV file
		printResult(final_solution);

		// the case that a solution has not been found
		if(!foundSolution)
			System.out.println("no solution found");
		// the case that a solution has been found
		else
			System.out.println("found solution in "+count+" iterations");
	}

	/*
	 * this function deep copy a matrix
	 * @param board_sol - the given matrix
	 * @return - a deep copy of the matrix
	 */
	private ArrayList<ArrayList<Integer>> copy(ArrayList<ArrayList<Integer>> board_sol)
	{
		ArrayList<ArrayList<Integer>> board_sol2 = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> row,new_row;

		// for every row
		for (int i = 0; i < board_sol.size(); i++) 
		{
			row = board_sol.get(i);
			new_row = new ArrayList<Integer>();

			// for every column
			for (int j = 0; j < row.size(); j++) 
			{
				// copy the cell
				new_row.add(row.get(j));
			}

			board_sol2.add(new_row);
		}
		
		return board_sol2;
	}

	/*
	 * this function optimize a given populatin of chromosome
	 * @param population - the current population
	 * @return - the optimized population
	 */
	private ArrayList<Chromosome> opt(ArrayList<Chromosome> population)
	{
		int row,col;
		ArrayList<Chromosome> population2 = new ArrayList<Chromosome>();
		Chromosome chromosome, temp, temp2;
		Random r = new Random();
		double oldFitness, newFItness;
		ArrayList<ArrayList<Integer>> board_sol;
		ArrayList<ArrayList<Integer>> board_sol2;
		
		// for every chromosome
		for (int i=0 ; i<population.size(); i++) 
		{
			chromosome = population.get(i);
			board_sol = chromosome.getData();
			temp = copy2(chromosome);
			// perform (BOARD_SIZE_COL+BOARD_SIZE_ROW) optimizations on the current chromosome
			for (int j = 0; j < BOARD_SIZE_COL+BOARD_SIZE_ROW; j++) 
			{
				board_sol2 = copy(board_sol);
				oldFitness = temp.evaluateFitness();
				
				row = r.nextInt(BOARD_SIZE_ROW);
				col = r.nextInt(BOARD_SIZE_COL);

				//board sol2 change
				board_sol2.get(row).set(col, 1-(board_sol2.get(row).get(col)));

				temp2 = new GriddlersChromosome(board_sol2);
				newFItness = temp2.evaluateFitness();
				// the case that the change was good (improved the fitness)
				if(newFItness > oldFitness)
				{
					// keep the change
					temp = copy2(temp2);
					board_sol = copy(board_sol2);
				}
				// the case that the change wasn't good (didn't improve the fitness)
				else
				{
					board_sol2 = copy(board_sol);
				}
			}
			population2.add(temp);
		}
		return population2;
	}

	/*
	 * this function deep copy a chromosome
	 * @param chromosome - the given chromosome
	 * @return - a deep copy of the chromosome
	 */
	private Chromosome copy2(Chromosome chromosome) 
	{
		Chromosome temp;
		ArrayList<ArrayList<Integer>> board_sol, board_sol2;
		board_sol = chromosome.getData();
		// deep copy the matrix
		board_sol2 = copy(board_sol);
		temp = new GriddlersChromosome(board_sol2);
		return temp;
	}

	/*
	 * this function returns the chromosome with the best fitness in the population
	 * @param population - the current population
	 * @return - the best chromosome in the population
	 */
	private Chromosome getBestSolution(ArrayList<Chromosome> population) 
	{
		int max_fitness=-1;
		int max_index=-1;

		// for every chromosome in the population 
		for(int i=0;i<population.size();i++)
		{
			// the case that this chromosome's fitness is bigger then the current maximal
			if(population.get(i).evaluateFitness()>max_fitness)
			{
				// update the maxium fitness
				max_fitness=(int) population.get(i).evaluateFitness();
				max_index=i;
			}
		}

		Chromosome best=population.get(max_index);
		return best;
	}

	/*
	 * this function returns the chromosome with the best fitness in the population
	 * and removes the worst one 
	 * @param population - the current population
	 * @param right - the best fitness possiable
	 * @return - the best chromosome
	 */
	private Chromosome getMaxAndRemoveWorst(ArrayList<Chromosome> population, int right)
	{
		int max_fitness=-1;
		int max_index=-1;

		int min_fitness = right+10; 
		int min_index=-1;

		// for every chromosome in the population 
		for(int i=0;i<population.size();i++)
		{
			// the case that this chromosome's fitness is bigger then the current maximal
			if(population.get(i).evaluateFitness()>max_fitness)
			{
				// update the maxium fitness
				max_fitness=(int) population.get(i).evaluateFitness();
				max_index=i;
			}

			// the case that this chromosome's fitness is lower then the current minimal
			if(population.get(i).evaluateFitness()<min_fitness)
			{
				// update the minimum fitness
				min_fitness=(int) population.get(i).evaluateFitness();
				min_index=i;
			}
		}

		Chromosome best;

		// the case that the whole population has the same fitness
		if(max_index == min_index)
		{
			best=population.get(1);
			// remove the worst
			population.remove(0);
		}
		// the case that the whole population doesn't have the same fitness
		else
		{
			best=population.get(max_index);
			// remove the worst
			population.remove(min_index);
		}
		return best;
	}

	/**
	 * this function initiate the first population of chromosomes with random values
	 * @param size - the population size
	 * @return - the first population
	 */
	@Override
	public ArrayList<Chromosome> initiate_population(int size) 
	{
		Random r = new Random();
		ArrayList<Chromosome> population=new ArrayList<Chromosome>(size);
		int num;	
		ArrayList<Integer> temp;
		ArrayList<ArrayList<Integer>> board_sol;

		// for every chromosome
		for(int i=0;i<size;i++)
		{
			board_sol = new ArrayList<ArrayList<Integer>>();
			// for every row
			for (int j = 0; j < BOARD_SIZE_ROW; j++) 
			{
				temp = new ArrayList<Integer>();
				// for every col
				for (int j2 = 0; j2 < BOARD_SIZE_COL; j2++) 
				{
					// generate a random cell value
					num = r.nextInt(2);
					temp.add(num);
				}
				board_sol.add(temp);
			}
			population.add(new GriddlersChromosome(board_sol));
		}
		return population;
	}

	/*
	 * this function calculate the exp value for the i-th chromosome in the population
	 * @param i - the index for the chromosome
	 * @param population - the current population
	 * @param avg - this population fitness's average
	 * @return - the exp value
	 */
	private double ExpVal(int i,ArrayList<Chromosome> population,double avg)
	{
		// the case that the avaage is 0
		if(avg == 0)
		{
			return 1;
		}

		return (population.get(i).evaluateFitness())/avg;
	}

	/*
	 * this function calculates the average fitness of the given population
	 * @param population - the current population
	 * @return - the average fitness of this population
	 */
	private double calcAvgFitness(ArrayList<Chromosome> population)
	{
		double sum=0;

		// for every chromosome in the population
		for(Chromosome chrm:population)
		{
			// add this chromosome fitness
			sum+=chrm.evaluateFitness();
		}

		// return the average fitness
		return ((double)sum)/population.size();
	}

	/**
	 * this function selects the parents for the crossover operation
	 * @param population - the current population
	 * @return - the selected parents for the crossover
	 */
	@Override
	public ArrayList<Chromosome> selection(ArrayList<Chromosome> population)
	{
		// calculating the average fitness
		double avg=calcAvgFitness(population);
		int N=population.size();
		int T = N;

		Random r=new Random();
		// get a random number
		double num=r.nextInt(T);
		double sum = 0.0;
		int j;

		ArrayList<Chromosome> selected=new ArrayList<Chromosome>();

		// choose N parents
		for(int i=0;i<N;i++)
		{
			// for each chromosome in the population
			for(j=0;j<N;j++)
			{
				// add the exp value to the sum
				sum+=ExpVal(j,population,avg);
				// the case that this "j" chromosome was selected
				if(sum>num)
				{	
					selected.add(population.get(j));
					// change in fixed distance
					num = (num+((double)T/N)) % T;
					sum = 0.0;
					break;
				}
			} 
		}

		return selected;
	}

	/**
	 * this function returns two children from the reproduction of parent1 and parent2
	 * @param parent1 - the first parent chromosome
	 * @param parent2 - the second parent chromosome
	 * @return - the two children of this parents
	 */
	@Override
	public ArrayList<Chromosome> crossover(Chromosome parent1,
			Chromosome parent2) {
		Random r=new Random();

		ArrayList<Chromosome> children=new ArrayList<Chromosome>();

		ArrayList<ArrayList<Integer>> child1=new ArrayList<ArrayList<Integer>>();
		ArrayList<ArrayList<Integer>> child2=new ArrayList<ArrayList<Integer>>();
		Chromosome p1_t, p2_t;
		int num;

		// get a random number (between 0 and 100)
		num=r.nextInt(100);

		// the case that this time the two parents will continue to the next generation with no crossover
		if(num>=CROSSOVER_RATE)
		{
			children.add(parent1);
			children.add(parent2);
			return children;
		}

		num = r.nextInt(2);
		// the case that the crossover will be based on rows
		if(num==0)
		{
			// for every row
			for (int i = 0; i < BOARD_SIZE_ROW; i++)
			{
				num=r.nextInt(2);
				// the case that the first child's row will be like parent one and the second child will be like parent two
				if(num==0)
				{
					child1.add(parent1.getData().get(i));
					child2.add(parent2.getData().get(i));
				}
				// the case that the first child's row will be like parent two and the second child will be like parent one
				else
				{
					child1.add(parent2.getData().get(i));
					child2.add(parent1.getData().get(i));
				}
			}
		}
		// the case that the crossover will be based on columns
		else
		{
			// working with the transposed parents (for columns)
			p1_t = new GriddlersChromosome(transpose(parent1.getData()));
			p2_t = new GriddlersChromosome(transpose(parent2.getData()));

			// for every col
			for (int i = 0; i < BOARD_SIZE_COL; i++)
			{
				num=r.nextInt(2);
				// the case that the first child's col will be like parent one and the second child will be like parent two
				if(num==0)
				{
					child1.add(p1_t.getData().get(i));
					child2.add(p2_t.getData().get(i));
				}
				// the case that the first child's col will be like parent two and the second child will be like parent one
				else
				{
					child1.add(p2_t.getData().get(i));
					child2.add(p1_t.getData().get(i));
				}
			}
			child1 = transpose(child1);
			child2 = transpose(child2);
		}

		// add the children to the result array (with possiable mutation)
		children.add(mutation(new GriddlersChromosome(child1)));
		children.add(mutation(new GriddlersChromosome(child2)));
		return children;
	}

	/**
	 * this function randomly changes chrm at certain probability
	 * @param chrm - the chromosome to change (maybe)
	 * @return - the chromosme after the change
	 */
	@Override
	public Chromosome mutation(Chromosome chrm) 
	{
		Random r = new Random();
		int num;

		num = r.nextInt(MUTATION_RATE);
		// the case that this chromosome will have a mutation on him
		if(num == 0)
		{
			ArrayList<ArrayList<Integer>> board_sol=chrm.getData();
			ArrayList<ArrayList<Integer>> board_sol2=copy(board_sol);

			// for every row
			for (int i = 0; i < BOARD_SIZE_ROW; i++) 
			{
				// for every col
				for (int j = 0; j < BOARD_SIZE_COL; j++) 
				{
					num = r.nextInt(10);
					// the case that this cell will change
					if (num == 0)
					{
						board_sol2.get(i).set(j, 1-(board_sol2.get(i).get(j)));
					}
				}
			}
			return new GriddlersChromosome(board_sol2);
		}
		// the case that this chromosome will not have a mutation on him
		else
		{
			return chrm;
		}
	}

	/*
	 * this function transpose the given matrix
	 * @param board_sol - the in[ut matrix
	 * @return - the given matrix transposed
	 */
	private ArrayList<ArrayList<Integer>> transpose(ArrayList<ArrayList<Integer>> board_sol)
	{
		ArrayList<ArrayList<Integer>> board = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> temp, temp2;

		// for every column
		for (int i = 0; i < board_sol.get(0).size(); i++) 
		{
			temp = new ArrayList<Integer>();
			// for every row
			for (int j = 0; j < board_sol.size(); j++) 
			{
				// create a dummy array
				temp.add(-1);
			}
			board.add(temp);	
		}

		// for every row
		for (int i = 0; i < board_sol.size(); i++) 
		{
			temp2 = board_sol.get(i);
			// for every column
			for (int j = 0; j < temp2.size(); j++) 
			{
				// update the transpose array
				board.get(j).set(i, temp2.get(j));
			}
		}
		return board;
	}
}